package Solutions;

/*
*
*最佳直线
* 给定一个二维平面及平面上的 N 个点列表Points，其中第i个点的坐标为Points[i]=[Xi,Yi]。请找出一条直线，其通过的点的数目最多。
设穿过最多点的直线所穿过的全部点编号从小到大排序的列表为S，你仅需返回[S[0],S[1]]作为答案，若有多条直线穿过了相同数量的点，则选择S[0]值较小的直线返回，S[0]相同则选择S[1]值较小的直线返回。
* */
public class Solution17 {
}
class Solution017 {
    public int[] bestLine(int[][] points) {
        int[] res = new int[]{0,1}; // 默认直线上的两个点的下标为0和1
        int max = 2; // 最多的点数，初始值是2
        for (int i = 0; i < points.length; i++) {
            int x1 = points[i][0], y1 = points[i][1]; // 获取第i个点的坐标
            for (int j = i + 1; j < points.length; j++) {
                int x2 = points[j][0], y2 = points[j][1]; // 获取第j个点的坐标
                // 统一线上的点数
                int tmp = 2;
                // 确定在线上点的个数
                for (int k = j + 1; k < points.length; k++) {
                    int x3 = points[k][0], y3 = points[k][1]; // 获取第k个点的坐标
                    // 两点法确定是否在同一条直线上
                    if ((y1 - y2) * (x1 - x3) == (y1 - y3) * (x1 - x2)) {
                        tmp++;
                    }
                }
                if (tmp > max) {
                    res[0] = i; // 更新直线上的第一个点的下标
                    res[1] = j; // 更新直线上的第二个点的下标
                    max = tmp; // 更新最多的点数
                }
            }
        }
        return res; // 返回直线上的两个点的下标
    }
}